package com.lenl.arithmetic.sort;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-02 12:22
 * @description 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr={53,3,542,748,14,214};
        doRadixSort(arr);
    }


    //基数排序
    public static void doRadixSort(int[] arr){
        //1.得到数组中最大的数的位数
        int max=arr[0];
        for (int i=0;i<arr.length;i++){
            if(arr[i]>max)
                max=arr[i];
        }
        //得到最大的是几位数
        int maxLength=(max+"").length();

        //循环
        for (int i=0,n=1;i<maxLength;i++,n*=10){
            executeOnce(arr,n,i);
        }
    }

    public static void executeOnce(int[] arr,int times,int i){
        //定义二维数组表示10个桶，每个桶是一个一维数组
        int[][] bucket=new int[10][arr.length];
        //记录每个桶中数据的数量
        int[] bucketElementCounts=new int[10];

        for (int j=0;j<arr.length;j++){
            //取出元素的个位数/10位数/百位数...
            int digitOfElement=(arr[j]/times)%10;
            //放到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
            bucketElementCounts[digitOfElement]++;
        }

        //按照桶的顺序取出数据，放回原来数组
        int index=0;
        //遍历每一个桶，将桶中数据放到原数组
        for (int k=0;k<bucketElementCounts.length;k++){
            //如果桶中有数据，才放入到原数组
            if(bucketElementCounts[k]!=0){
                //循环该桶
                for (int l=0;l<bucketElementCounts[k];l++){
                    arr[index]=bucket[k][l];
                    index++;
                }
                //每个桶的个数计数归零
                bucketElementCounts[k]=0;
            }
        }

        //System.out.println("第"+(i+1)+"轮对个位数排序："+ Arrays.toString(arr));
    }
}
